#include "Terrain.h"
#include "ILApp.h"

#define POSSIBLE_NEIGHBOURS(x,y) { IntPoint(x-1, y), IntPoint(x-1, y+1), IntPoint(x, y+1), IntPoint(x+1, y+1),  \
									IntPoint(x+1, y), IntPoint(x+1, y-1), IntPoint(x, y-1), IntPoint(x-1, y-1) }

D3D11_INPUT_ELEMENT_DESC TerrainVertexDeclration[] = 
{
     { "POSITION", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0 },
     { "TEXCOORD", 0, DXGI_FORMAT_R32G32_FLOAT, 0, D3D11_APPEND_ALIGNED_ELEMENT , D3D11_INPUT_PER_VERTEX_DATA, 0 },
     { "NORMAL", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, D3D11_APPEND_ALIGNED_ELEMENT , D3D11_INPUT_PER_VERTEX_DATA, 0 },
	 { "TEXCOORD", 1, DXGI_FORMAT_R32_UINT, 0, D3D11_APPEND_ALIGNED_ELEMENT, D3D11_INPUT_PER_VERTEX_DATA, 0},
};

float DistanceH(IntPoint a, IntPoint b)
{
	return (float)(abs(a.x - b.x) + abs(a.y + b.y));
}

CTerrainVertex::CTerrainVertex( vec3 _pos, vec2 _uv, UINT _index ) : m_Position(_pos), m_UV(_uv), m_index(_index)
{
    m_Normal = vec3(0, 1, 0);
}

CTerrainVertex::CTerrainVertex()
{

}

D3D11_INPUT_ELEMENT_DESC* CTerrainVertex::GetVertexDeclration()
{
    return TerrainVertexDeclration;
}

void CTerrainPatch::CreateMesh( CHeightMap& HeightMap, RECT source, ID3D11Device* pDevice, int index, ID3DX11Effect* pEffect)
{
	static UINT vertIndex = 0;
    m_pDevice = pDevice;
    m_pEffect = pEffect;
    UINT width = source.right - source.left;
    UINT height = source.bottom - source.top;

    m_nVertices = (width + 1) * (height + 1);
    m_nTri = width * height * 2;

    m_pVertices = new CTerrainVertex[m_nVertices];

    for (int z = source.top, z0 = 0;  z <= source.bottom; z0++, z++)
    {
        for (int x = source.left, x0 = 0;  x <= source.right; x0++, x++)
        {
            vec3 pos = vec3((float)x, HeightMap.GetHeight(x, z), -(float)z);
            vec2 uv = vec2(0, 0);

            m_pVertices[z0 * (width + 1) + x0] = CTerrainVertex(pos, uv, vertIndex++);
        }
    }

    m_pIndex = new WORD[m_nTri * 3];
    m_nIndex = 0;
    for (int z = source.top, z0 = 0;  z < source.bottom; z0++, z++)
    {
        for (int x = source.left, x0 = 0;  x < source.right; x0++, x++)
        {
            //triangle 1
            m_pIndex[m_nIndex++] = z0 * (width + 1) + x0;
            m_pIndex[m_nIndex++] = z0 * (width + 1) + x0 + 1;
            m_pIndex[m_nIndex++] = (z0 + 1) * (width + 1) + x0;

            //triangle 2
            m_pIndex[m_nIndex++] = (z0 + 1) * (width + 1) + x0;
            m_pIndex[m_nIndex++] = z0 * (width + 1) + x0 + 1;
            m_pIndex[m_nIndex++] = (z0 + 1) * (width + 1) + x0 + 1;

        }
    }


    ComputeNormals();
    CreateInputLayout();
    CD3DHelper::CreateVertexBuffer(m_pDevice, m_pVertices, sizeof(CTerrainVertex), m_nVertices, m_pVertexBuffer);
    CD3DHelper::CreateIndexBuffer(m_pDevice, m_pIndex, sizeof(WORD), m_nIndex, m_pIndexBuffer);
}

void CTerrainPatch::ComputeNormals()
{
    
}

void CTerrainPatch::Render()
{
    ID3D11DeviceContext* pContext = NULL;
    m_pDevice->GetImmediateContext(&pContext);
    UINT stride = sizeof(CTerrainVertex);
    UINT offset = 0;

    pContext->IASetInputLayout(m_pInputLayout);
    pContext->IASetVertexBuffers( 0, 1, &m_pVertexBuffer, &stride, &offset );

    pContext->IASetIndexBuffer(m_pIndexBuffer, DXGI_FORMAT_R16_UINT, 0);

    pContext->IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST);
    ID3DX11EffectPass* pEffectPass = m_pEffect->GetTechniqueByIndex(0)->GetPassByIndex(0);
    pEffectPass->Apply(0, pContext);
    pContext->DrawIndexed(m_nIndex, 0, 0);
}

void CTerrainPatch::CreateInputLayout()
{
    D3D11_INPUT_ELEMENT_DESC* layout = CTerrainVertex::GetVertexDeclration();
    UINT numElements = 4;

    ID3DX11EffectPass* pEffectPass = m_pEffect->GetTechniqueByIndex(0)->GetPassByIndex(0);

    D3DX11_PASS_SHADER_DESC effectVsDesc;
    pEffectPass->GetVertexShaderDesc(&effectVsDesc);
    D3DX11_EFFECT_SHADER_DESC effectVsDesc2;
    effectVsDesc.pShaderVariable->GetShaderDesc(effectVsDesc.ShaderIndex, &effectVsDesc2);
    const void *vsCodePtr = effectVsDesc2.pBytecode;
    unsigned vsCodeLen = effectVsDesc2.BytecodeLength;


    m_pDevice->CreateInputLayout(layout , numElements, vsCodePtr, vsCodeLen, &m_pInputLayout );
}

CTerrainPatch::CTerrainPatch()
{
    
}

CTerrainPatch::~CTerrainPatch()
{
	SAFE_DELETE_ARRAY(m_pVertices);
	SAFE_DELETE_ARRAY(m_pIndex);
}

IntPoint CTerrainPatch::GetPointFromVertexIndex( int VertexIndex ) const
{
	CTerrainVertex Vertex =  m_pVertices[VertexIndex];
	int x = (int)Vertex.m_Position.x;
	int y = -(int)Vertex.m_Position.z;
	return IntPoint(x,y);
}

//return the world position form the map position
vec3 CTerrain::GetWorldPos(IntPoint mapPos)
{
	return vec3((float)mapPos.x, m_pHeightMap->GetHeight(mapPos.x, mapPos.y), -(float)mapPos.y);
}

void CTerrain::CreateTerrainEffectFile()
{
    ID3D10Blob *effectBlob = NULL, *errorsBlob = NULL;
    HRESULT hr = D3DX11CompileFromFile(
        "..\\Shaders\\Tutorial02.fx", 0, 0, 0, "fx_5_0", 0, 0, 0, &effectBlob, &errorsBlob, 0);

	if (errorsBlob)
	{
		char* errorlog = (char*)errorsBlob->GetBufferPointer();
		printf("%s\n", errorlog);
	}
    hr = D3DX11CreateEffectFromMemory(
        effectBlob->GetBufferPointer(), effectBlob->GetBufferSize(), 0, m_pDevice, &m_pEffect, D3D_FEATURE_LEVEL_10_0);
}

UINT CTerrainPatch::GetSize() const
{
	return m_nVertices;
}

void CTerrain::Init( ID3D11Device* _pDevice, IntPoint _size, CILApp* pApp)
{
    m_pApp = pApp;
    m_pDevice = _pDevice;
    m_size = _size;
    m_pHeightMap = new CHeightMap(1, 1);
    CreateTerrainEffectFile();
    CreatePatches(10);

	InitPathFinding();

	m_CurrVertex = 0;
	for (int i = 0; i < 2; i++)
	{
		m_MarkedVertex[i] = -1;
	}
}



UINT CTerrain::GetPatchSize() const
{
	return m_patches[1]->GetSize();
}

void CTerrain::CreatePatches( int nPatches )
{
    for (int y = 0; y < nPatches; y++)
    {
        for (int x = 0; x < nPatches; x++)
        {
            RECT r = { x * (m_size.x - 1) / nPatches, 
                y * (m_size.y - 1) / nPatches, 
                (x + 1) * (m_size.x - 1) / nPatches, 
                (y + 1) * (m_size.y - 1) / nPatches, };

            CTerrainPatch* patch = new CTerrainPatch();
            patch->CreateMesh(*m_pHeightMap, r, m_pDevice, (int)m_patches.size(), m_pEffect);
            m_patches.push_back(patch);
        }
    }
}

CTerrain::CTerrain()
{

}

void CTerrain::Render()
{
    D3D11_RASTERIZER_DESC desc;
    ZeroMemory(&desc, sizeof(desc));
    ID3D11RasterizerState* ppRasterizerState = NULL;
    desc.CullMode = D3D11_CULL_NONE;
    desc.FillMode = D3D11_FILL_WIREFRAME;
    m_pDevice->CreateRasterizerState(&desc, &ppRasterizerState);
    ID3D11DeviceContext* pc;
    m_pDevice->GetImmediateContext(&pc);
    pc->RSSetState(ppRasterizerState);
    CCamera* pCamera = m_pApp->GetCamera();
    mat4 Proj = pCamera->GetProjectionMatrix();
    mat4 View = pCamera->GetViewMatrix();
    m_pEffect->GetVariableByName("Proj")->AsMatrix()->SetMatrix((float*)Proj);
    m_pEffect->GetVariableByName("View")->AsMatrix()->SetMatrix((float*)View);
	m_pEffect->GetVariableByName("markedV")->AsVector()->SetIntVector((int*)m_MarkedVertex);
    for (UINT i = 0; i < m_patches.size(); i++)
    {
        m_patches[i]->Render();
    }

	if (!m_Path.bEmpty)
	{
		m_Path.Render();
	}
}

void CTerrain::InitPathFinding()
{
	m_nTiles = m_size.x * m_size.y;
	m_pMapTiles = new CMapTile[m_nTiles];

	//init tiles
	for(int y=0;y<m_size.y;y++)
	{
		for(int x=0;x<m_size.x;x++)
		{
			CMapTile *pTile = GetTile(x, y);
			pTile->m_height = m_pHeightMap->GetHeight(x, y);
			pTile->m_MapPos = IntPoint(x, y);
		}
	}

	//calculate cost for tiles
	for (int y = 0; y < m_size.y; y++)
	{
		for (int x = 0; x < m_size.x; x++)
		{
			CMapTile* pTile = GetTile(x, y);
			assert(pTile);

			IntPoint P[] = POSSIBLE_NEIGHBOURS(x,y);
			float variance = 0.0f;
			int nNeighbour = 0;

			for (int i = 0; i < 8; i++)
			{
				CMapTile* pNeighbourTile = GetTile(P[i]);

				if (pNeighbourTile)
				{
					float v = pNeighbourTile->m_height - pTile->m_height;
					variance += v * v;
					nNeighbour++;
				}
			}

			//cost = height variance
			variance /= (float)nNeighbour;
			pTile->m_cost = min(variance + 0.1f, 1.0f);

			//if tile cost is less than 1.0 then we can walk on the tile;
			pTile->m_walkable = pTile->m_cost < 1.0f;
			
		}
	}

	//connect the graph
	for (int y = 0; y < m_size.y; y++)
	{
		for (int x = 0; x < m_size.x; x++)
		{
			CMapTile* pTile = GetTile(x, y);
			if (pTile && pTile->m_walkable)
			{
				//clear old neighbours
				pTile->ClearNeighbours();

				IntPoint P[] = POSSIBLE_NEIGHBOURS(x, y);

				for (int i = 0; i < 8; i++)
				{
					if (Within(P[i]))
					{
						CMapTile* pNeighbourTile = GetTile(P[i]);

						if (pNeighbourTile && pNeighbourTile->m_walkable)
						{
							pTile->m_pNeighbors[i] = pNeighbourTile;
						}
					}
				}
			}
		}
	}

	CreateTileSets();
}

bool CTerrain::Within( IntPoint P )
{
	bool bInBoundX = P.x < m_size.x && P.x >=0;
	bool bInBoundY = P.y < m_size.y && P.y >= 0;

	return bInBoundX && bInBoundY;
}

//TODO change this algorithm to BFS
void CTerrain::CreateTileSets()
{
	int SetNo = 0;

	for (int y = 0; y < m_size.y; y++)
	{
		for (int x = 0; x < m_size.x; x++)
		{
			CMapTile* pTile = GetTile(x,y);
			pTile->m_set = SetNo++;
		}
	}

	bool changed = true;
	while (changed)
	{
		changed = false;
		for (int y = 0; y < m_size.y; y++)
		{
			for (int x = 0; x < m_size.x; x++)
			{
				CMapTile* pTile = GetTile(x,y);

				if (pTile && pTile->m_walkable)
				{
					for (int i = 0; i < 8; i++)
					{
						CMapTile* pNeighbour = pTile->m_pNeighbors[i];

						if (pNeighbour && pNeighbour->m_walkable && pNeighbour->m_set < pTile->m_set)
						{
							changed = true;
							pTile->m_set = pNeighbour->m_set;
						}
					}
				}
			}
		}
		
	}
}

Path CTerrain::GetPath( IntPoint start, IntPoint goal )
{
	CMapTile* pStartTile = GetTile(start);
	CMapTile* pGoalTile = GetTile(goal);

	//bad arguments no path 
	if(pStartTile == pGoalTile || pStartTile == NULL || pGoalTile == NULL)
	{
		return Path();
	}

	// there is no path between the points
	if(!pStartTile->m_walkable || !pGoalTile->m_walkable || pStartTile->m_set != pGoalTile->m_set)
	{
		return Path();
	}

	//Init Search
	for(UINT l = 0; l < m_nTiles; l++)
	{
		m_pMapTiles[l].f = m_pMapTiles[l].g = FLT_MAX;		    //Clear F,G
		m_pMapTiles[l].bOpen = m_pMapTiles[l].bClosed = false;	//Reset Open and Closed
	}

	std::vector<CMapTile*> open;

	pStartTile->g = 0;
	pStartTile->f = DistanceH(start, goal);
	pStartTile->bOpen = true;
	open.push_back(pStartTile);

	bool found = false;
	while(!found && !open.empty())
	{
		//find tile with lowest F
		UINT bestIndex = 0;
		CMapTile* pBestTile = open[bestIndex];
		
		for (UINT i = 1; i < open.size(); i++)
		{
			CMapTile* pCurrTile = open[i];
			if (pCurrTile->f < pBestTile->f)
			{
				pBestTile = pCurrTile;
				bestIndex = i;
			}
		}

		if (pBestTile == NULL)
		{
			break; // no path found;
		}

		//remove best from open list
		open[bestIndex]->bOpen = false;
		open.erase(open.begin() + bestIndex);

		if(pBestTile == pGoalTile)		//If the goal has been found
		{
			assert(pBestTile->m_MapPos == pGoalTile->m_MapPos);
			Path path, reversedPath;
			CMapTile *pCurrTile = pBestTile;

			while(pCurrTile != pStartTile)	// Generate path
			{
				path.push_back(pCurrTile->m_MapPos);
				pCurrTile = pCurrTile->m_pParent;
			}

			// Reverse path
			for(int i=path.size()-1;i!=0;i--)
			{
				reversedPath.push_back(path[i]);
			}
			reversedPath.push_back(goal);
			return reversedPath;
		}
		else
		{
			for(int i=0; i<8; i++)		// otherwise, check the neighbors of the
			{
				if(pBestTile->m_pNeighbors[i] != NULL)	// best tile
				{
					bool inList = false;		    // Generate new G and F value
					float newG = pBestTile->g + 1.0f;
					float d = DistanceH(pBestTile->m_MapPos, pBestTile->m_pNeighbors[i]->m_MapPos);
					float newF = newG + DistanceH(pBestTile->m_pNeighbors[i]->m_MapPos, goal) + pBestTile->m_pNeighbors[i]->m_cost * 5.0f * d;

					if(pBestTile->m_pNeighbors[i]->bOpen || pBestTile->m_pNeighbors[i]->bClosed)
					{
						if(newF < pBestTile->m_pNeighbors[i]->f)	    // If the new F value is lower
						{
							pBestTile->m_pNeighbors[i]->g = newG;	// update the values of this tile
							pBestTile->m_pNeighbors[i]->f = newF;
							pBestTile->m_pNeighbors[i]->m_pParent = pBestTile;								
						}
						inList = true;
					}

					if(!inList)			// If the neighbor tile isn't in the Open or Closed list
					{
						pBestTile->m_pNeighbors[i]->f = newF;		//Set the values
						pBestTile->m_pNeighbors[i]->g = newG;
						pBestTile->m_pNeighbors[i]->m_pParent = pBestTile;
						pBestTile->m_pNeighbors[i]->bOpen = true;
						open.push_back(pBestTile->m_pNeighbors[i]);	//Add it to the open list	
					}
				}

				pBestTile->bClosed = true;		//The best tile has now been searched, add it to the Closed list
			}
		}
	}

	return Path();		//No path found, return an empty path

}

Path CTerrain::GetPath( int StartVertexIndex, int EndVertexIndex )
{
	if (StartVertexIndex == -1 || EndVertexIndex == -1)
	{
		return Path();
	}

	IntPoint StartPoint = GetPointFromVertexIndex(StartVertexIndex);
	IntPoint EndPoint = GetPointFromVertexIndex(EndVertexIndex);
	Path path = GetPath(StartPoint, EndPoint);
	path.insert(path.begin(), StartPoint);
	return path;
}

CTerrain::~CTerrain()
{
	while(!m_patches.empty())
	{
		CTerrainPatch* pPatch = m_patches.back();
		SAFE_DELETE(pPatch);
		m_patches.pop_back();
	}
	
	SAFE_DELETE_ARRAY(m_pMapTiles);
	SAFE_DELETE(m_pHeightMap);
}

CMapTile* CTerrain::GetTile( int x, int y )
{
	return m_pMapTiles + x + y * m_size.x;
}

CMapTile* CTerrain::GetTile( IntPoint p )
{
	if (Within(p))
	{
		return GetTile(p.x, p.y);
	}
	else
	{
		return NULL;
	}
}

void CTerrain::MarkTerrainVertex( int ObjectIndex )
{
	m_MarkedVertex[m_CurrVertex] = ObjectIndex;
	m_CurrVertex = (m_CurrVertex + 1) & 0x1;

	if (m_CurrVertex == 0)
	{
		Path path = GetPath(m_MarkedVertex[0], m_MarkedVertex[1]);

		if (path.empty())
		{
			return;
		}

		vec3* nodes = new vec3[path.size()];
		for (UINT i = 0; i < path.size(); i++)
		{
			CMapTile* pTile = GetTile(path[i]);
			nodes[i] = vec3(pTile->m_MapPos.x, pTile->m_height, -pTile->m_MapPos.y);
		}

		CPath PathMesh(nodes, m_pDevice, path.size(), m_pEffect);
		m_Path = PathMesh;
		delete nodes;
	}
}

IntPoint CTerrain::GetPointFromVertexIndex( int VertexIndex ) const
{
	UINT LastPatchSize = 0;
	int CurrVertexIndex = VertexIndex;
	//Patches are not uniform in size
	for (UINT i = 0; i < m_patches.size(); i++)
	{
		CTerrainPatch* pPatch = m_patches[i];
		UINT PatchSize = pPatch->GetSize();
		
		
		if (CurrVertexIndex < PatchSize)
		{
			IntPoint VertexLocation = pPatch->GetPointFromVertexIndex(CurrVertexIndex % PatchSize);
			return VertexLocation;
		}
		else
		{
			CurrVertexIndex = CurrVertexIndex - PatchSize;
			LastPatchSize = PatchSize;
		}
	}
	
	
}

void CMapTile::ClearNeighbours()
{
	for (int i = 0; i < 8; i++)
	{
		m_pNeighbors[i] = NULL;
	}
}

CMapTile::CMapTile()
{
	ZeroMemory(this, sizeof(CMapTile));
}

CPath::CPath( vec3* path, ID3D11Device* pDevice, int PathSize, ID3DX11Effect* pEffect ) : m_size(PathSize), m_pDevice(pDevice), m_pEffect(pEffect), m_pInputLayout(NULL),
																						  m_pVertexBuffer(NULL)
{
	static D3D11_INPUT_ELEMENT_DESC layout[] = 
	{
		 { "POSITION", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0 },
	};

	ID3DX11EffectPass* pPass = m_pEffect->GetTechniqueByName("RenderPath")->GetPassByIndex(0);

	CD3DHelper::CreateVertexBuffer(m_pDevice, path, sizeof(vec3), m_size, m_pVertexBuffer);
	CD3DHelper::CreateInputLayout(m_pDevice, layout, ARRAYSIZE(layout), pPass, m_pInputLayout );

	bEmpty = m_size == 0;

}

CPath::CPath()
{

}

void CPath::Render()
{
	UINT stride = sizeof(vec3);
	UINT offset = 0;
	ID3D11DeviceContext* pContext = CD3DHelper::GetImmediateContext(m_pDevice);
	pContext->IASetVertexBuffers(0, 1, &m_pVertexBuffer, &stride, &offset);
	pContext->IASetInputLayout(m_pInputLayout);
	pContext->IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_LINESTRIP);
	ID3DX11EffectPass* pEffectPass = m_pEffect->GetTechniqueByIndex(1)->GetPassByIndex(0);
	pEffectPass->Apply(0, pContext);
	pContext->Draw(m_size, 0);
}
